package com.gwcloud.leetcode.interview100;

import java.util.ArrayList;
import java.util.List;

/** 
* @ClassName   : Leetcode0212 
* @author      : ganwei 
* @date        : 2020年5月29日 
* @Description : TODO 
*/
public class Leetcode0212 {
	List<String> result = new ArrayList<>();
    /**
     * -解题思路，回溯
     */
	public List<String> findWords(char[][] board, String[] words) {
    	for(String word : words) {
    		if(exist(board,word)) {
    			result.add(word);
    		}
    	}
    	
    	return result;
    }
	
    public boolean exist(char[][] board, String word) {
    	if(board.length == 0 || word.length() == 0) {
    		return false;
    	}

    	for(int i = 0; i < board.length; i++) {
    		for(int j = 0; j < board[i].length; j++) {
    			if(backtrack(board,word,new boolean[board.length][board[0].length],i,j)) {
    				return true;
    			}
    		}
    	}
    	
    	return false;
    }

    /**
     * -回溯主体
     */
    public boolean backtrack(char[][] board, String word, boolean[][] isVisited, int i, int j) {

    	if(word.isEmpty()) {
    		return true;
    	}
    	
    	if(board[i][j] == word.charAt(0) && word.length() == 1){
            return true;
        }

    	if(board[i][j] == word.charAt(0)) {
    		isVisited[i][j] = true;
    		if(i+1 >= 0 && i+1 < board.length && !isVisited[i+1][j]) {
    			
    			if(backtrack(board, word.substring(1), isVisited, i+1, j)) {
    				return true;
    			}
    			
    		}
    		if(j+1 >= 0 && j+1 < board[i].length && !isVisited[i][j+1]) {
    			
    			if(backtrack(board, word.substring(1), isVisited, i, j+1)) {
    				return true;
    			}
    			
    		}
    		if(i-1 >= 0 && i-1 < board.length && !isVisited[i-1][j]) {
    			
    			if(backtrack(board, word.substring(1), isVisited, i-1, j)) {
    				return true;
    			}
    			
    		}
    		if(j-1 >= 0 && j-1 < board[i].length && !isVisited[i][j-1]) {
    			
    			if(backtrack(board, word.substring(1), isVisited, i, j-1)) {
    				return true;
    			}
    			
    		}
    		isVisited[i][j] = false;
    		
    	}

    	return false;
    	
    } 
    
    /**
     * -单词搜索,主函数
     */
    public static void main(String[] args) {
    	
    }
    
}
